package dp.maxsum;

public class 面试题1724最大子矩阵 {
    int row1,row2,col1,col2;
    int col1Tem,col2Tem;
    public int[] getMaxMatrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] matrixSum = new int[row][col];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < row; i++) {
            for (int k = 0; k < col; k++) {
                if (i == 0) {
                    matrixSum[i][k] = matrix[i][k];
                } else {
                    matrixSum[i][k] = matrixSum[i - 1][k] + matrix[i][k];
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j <= i; j++) {
                int[] nums = new int[col];
                for (int k = 0; k < col; k++) {
                    if (j == 0) {
                        nums[k] = matrixSum[i][k];
                    } else {
                        nums[k] = matrixSum[i][k] - matrixSum[j - 1][k];
                    }

                }
                int temMax = getMaxSum(nums);
                if (temMax > max) {
                    max = temMax;
                    row1 = j;
                    row2 = i;
                    col1 = col1Tem;
                    col2 = col2Tem;
                }
            }
        }
        return new int[]{ row1, col1, row2, col2 };
    }

    private int getMaxSum(int[] nums) {
        int temMax = nums[0];
        int max = nums[0];
        int length = nums.length;
        int temCol1 = 0;
        for (int i = 1; i < length; i++) {
            if (temMax > 0) {
                temMax = temMax + nums[i];
            } else {
                temMax = nums[i];
                temCol1 = i;
            }
            if (temMax > max) {
                max = temMax;
                col1Tem = temCol1;
                col2Tem = i;
            }
        }
        return max;
    }
}
